package cn.dlc.com.tree;

import cn.dlc.com.queue.Queue;
import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;

/**
 * @author 邓立川
 * @date 2021/3/22 20:37
 * @desc 当前类的描述信息
 */
@Data
public class BinaryTree<Key extends Comparable<Key>,Value> {

    @Data
    @AllArgsConstructor
    @NoArgsConstructor
    private class Node<Key extends Comparable<Key> ,Value> {
        // 键
        private Key key;
        // 值
        private Value value;
        // 左子节点
        private Node<Key, Value> left;
        // 右子结点
        private Node<Key, Value> right;
    }

    // 根节点
    private Node<Key, Value> root;
    // 元素个数
    private int num;

    public BinaryTree(){
        this.root = null;
        this.num = 0;
    }

    public int size(){
        return this.num;
    }

    // 添加节点
    public void put(Key key,Value value){
        // 接收这个值
        this.root = put(this.root,key,value);
    }

    // 重载添加节点的方法
    private Node<Key,Value> put(Node<Key,Value> x, Key key,Value value) {
        // 如果子树为空的话，那么添加的这个就是子树的根节点，直接返回
        if(x == null) {
            this.num++;
            // 直接返回这个节点
            x = new Node<>(key,value,null,null);
            return x;
        }

        // 比较一个当前的键和x节点，
        int com = key.compareTo(x.getKey());

        if(com > 0){
            // key更加大，那么放在右边，x的右子结点指向他
            x.right = put(x.right,key,value);
        }else if(com < 0) {
            // key小一些，放在左边，x的左子结点指向他
            x.left = put(x.left,key,value);
        } else {
            // 相等的话，替换新的值
            x.value = value;
        }

        return x;
    }

    public Value get(Key key) {
        return get(this.root,key);
    }

    private Value get(Node<Key,Value> x, Key key) {

        if(x == null) {
            return null;
        }

        int com = key.compareTo(x.getKey());
        if(com > 0){
            // key更加大，那么放在右边，注意返回
            return get(x.right,key);
        }else if(com < 0) {
            // key小一些，放在左边，注意返回
            return get(x.left,key);
        } else {
            // 相等的话，替换新的值
            return x.getValue();
        }
    }

    public void delete(Key key) {
        delete(root, key);
    }

    /**
     * 返回删除后的新树（其实就是返回删除后的节点，）
     * @param x
     * @param key
     * @return
     */
    private Node<Key, Value> delete(Node<Key,Value> x, Key key) {

        if(x == null) {
            // 本来就是空的，没法删
            return null;
        }

        int com = key.compareTo(x.getKey());

        if(com > 0) {
            // 继续找
            x.right = delete(x.right, key);
        } else if(com < 0) {
            // 左边继续找
            x.left = delete(x.left,key);
        } else {

            // 先减掉这个元素
            this.num--;

            // 找到了
            if(x.getRight() == null) {
                // 没有右子树了，左子树作为替换后的元素
                return x.getLeft();
            }
            if(x.getLeft() == null) {
                // 没有左子树了，右子树作为替换后的元素
                return x.getRight();
            }

            // 找到右子树中的最小左子节点（用来替换被删掉的元素）
            Node<Key, Value> minNode = x.right;
            while(minNode.getLeft() != null) {
                minNode = minNode.getLeft();
            }

            // 断开最小左子节点和其父节点的联系
            Node<Key, Value> node = x.getRight();
            while(node.getLeft() != null) {
                if(node.getLeft().getLeft() == null) {
                    // 找到了最小的左子树，断开连接,就是把这个最小左子树空出来
                    node.setLeft(null);
                } else {
                    // 继续找
                    node = node.getLeft();
                }
            }

            // 完全替换掉x节点
            minNode.left = x.left;
            minNode.right = x.right;
            x = minNode;
        }

        return x;
    }

    public Key min() {
        return min(root).getKey();
    }

    private Node<Key,Value> min(Node<Key,Value> x) {
        if(x.getLeft() != null) {
            return min(x.getLeft());
        } else {
            return x;
        }
    }

    public Key max() {
        return max(root).getKey();
    }

    private Node<Key,Value> max(Node<Key,Value> x) {
        if(x.getRight() != null) {
            return min(x.getRight());
        } else {
            return x;
        }
    }


    // 前序遍历
    public Queue<Key> preErgodic(){
        Queue<Key> keys = new Queue<>();
        // 从根节点开始，将所有的键按照顺序放进keys里面去
        preErgodic(this.root, keys);
        return keys;
    }

    private void preErgodic(Node<Key,Value> x, Queue<Key> keys) {
        //
        if(x == null) {
            return ;
        }

        // 先把当前节点放到key里面去
        keys.enQueue(x.getKey());

        // 如果左子节点部位空，递归方进去
        if(x.getLeft() != null) {
            preErgodic(x.getLeft(),keys);
        }

        if(x.getRight() != null) {
            preErgodic(x.getRight(), keys);
        }
    }


    // 中序遍历
    public Queue<Key> midErgodic(){
        Queue<Key> keys = new Queue<>();
        // 从根节点开始，将所有的键按照顺序放进keys里面去
        midErgodic(this.root, keys);
        return keys;
    }

    private void midErgodic(Node<Key,Value> x, Queue<Key> keys) {
        //
        if(x == null) {
            return ;
        }

        // 如果左子节点部位空，递归方进去
        if(x.getLeft() != null) {
            midErgodic(x.getLeft(),keys);
        }
        // 把当前节点放到key里面去（前面的左子节点为空，那么这个就是最左的了）
        keys.enQueue(x.getKey());

        // 递归遍历右子树
        if(x.getRight() != null) {
            midErgodic(x.getRight(), keys);
        }
    }


    // 后续遍历
    public Queue<Key> lastErgodic(){
        Queue<Key> keys = new Queue<>();
        // 从根节点开始，将所有的键按照顺序放进keys里面去
        lastErgodic(this.root, keys);
        return keys;
    }

    private void lastErgodic(Node<Key,Value> x, Queue<Key> keys) {
        //
        if(x == null) {
            return ;
        }

        // 如果左子节点部位空，递归方进去
        if(x.getLeft() != null) {
            lastErgodic(x.getLeft(),keys);
        }

        // 递归遍历右子树
        if(x.getRight() != null) {
            lastErgodic(x.getRight(), keys);
        }

        // 把当前节点放到key里面去（前面的左子节点为空，那么这个就是最左的了）
        keys.enQueue(x.getKey());
    }

    // 层序遍历
    public Queue<Key> layerErgodic(){

        // 用来存放key
        Queue<Key> keys = new Queue<>();
        // 用来存放节点
        Queue<Node<Key,Value>> nodes = new Queue<>();

        // 先把根节点存放进去
        nodes.enQueue(this.root);

        while(!nodes.isEmpty()) {
            // 只要节点不为空，也就是没有遍历完
            // 出来一个
            Node<Key, Value> node = nodes.deQueue();
            // 出来的这个节点的key放到keys里面去
            keys.enQueue(node.getKey());

            if(node.getLeft()!= null) {
                nodes.enQueue(node.getLeft());
            }

            if(node.getRight() != null) {
                nodes.enQueue(node.getRight());
            }
        }
        return keys;
    }


    // 获取树的最大深度
    public int maxDepth(){
        return maxDepth(this.root);
    }

    private int maxDepth(Node<Key, Value> root) {
        if(root == null) {
            return 0;
        }

        int maxLeft = 0;
        int maxRight = 0;
        int max = 0;

        if(root.getLeft() != null){
            maxLeft = maxDepth(root.getLeft());
        }

        // 计算右子树的最大值
        if(root.getRight() != null){
            maxRight = maxDepth(root.getRight());
        }

        max = maxLeft > maxRight? maxLeft+1 : maxRight+1;

        return max;
    }









}
